package src.dp.bag01;

import java.util.Scanner;

public class kama56 {//多重背包，每种物品有多个但数量有限，选择装某种物品时就要将它的这几个全装上

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int bagWeight = sc.nextInt();
        int n = sc.nextInt();//物品种类
        int[] weight = new int[n];
        int[] value = new int[n];
        int[] nums = new int[n];
        int[] dp = new int[bagWeight + 1];

        for (int i = 0; i < n; i++) {
            weight[i] = sc.nextInt();
        }
        for (int i = 0; i < n; i++) {
            value[i] = sc.nextInt();
        }
        for (int i = 0; i < n; i++) {
            nums[i] = sc.nextInt();
        }

        for (int i = 0; i < n; i++) {
            //遍历背包倒序
            for (int j = bagWeight; j >= weight[i]; j--) {
                //多加一个维度 k 遍历每种物品的个数
                for (int k = 1; k <= nums[i] && j >= k * weight[i]; k++) {
                    dp[j] = Math.max( dp[j], dp[j - k * weight[i]] + k * value[i] );
                }
            }
        }
        System.out.println(dp[bagWeight]);

    }
}
